SIAM Journal on Computing -- 1991

By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

© SIAM

SIAM Journal on Computing

Table of Contents

Available Volumes| Issue Index| View myArticles

Search This Issue

Volume 20, Issue 2, pp. 209-404

Please Note: Electronic articles are available well in advance of the printed articles.

Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs

Egon Balas and Jue Xue

pp. 209-221

BibTeX Abstract Full Text: PDF

Approximate Levels in Line Arrangements

pp. 222-227

BibTeX Abstract Full Text: PDF

Parallel Algorithms for Channel Routing in the Knock-Knee Model

Joseph JáJá and Shing-Chong Chang

pp. 228-245

BibTeX Abstract Full Text: PDF

Some Observations on Separating Complexity Classes

pp. 246-258

BibTeX Abstract Full Text: PDF

An $O(n\log ^2 h)$ Time Algorithm for the Three-Dimensional Convex Hull Problem

Herbert Edelsbrunner and Weiping Shi

pp. 259-269

BibTeX Abstract Full Text: PDF

A general Sequential Time-Space Tradeoff for Finding Unique Elements

pp. 270-277

BibTeX Abstract Full Text: PDF

The Power of Alternating One-Reversal Counters and Stacks

Oscar H. Ibarra and Tao Jiang

pp. 278-290

BibTeX Abstract Full Text: PDF

Interpolation and Approximation of Sparse Multivariate Polynomials over $GF(2)$

Ron M. Roth and Gyora M. Benedek

pp. 291-314

BibTeX Abstract Full Text: PDF

Lower Bounds for Computations with the Floor Operation

Yishay Mansour, Baruch Schieber, and Prasoon Tiwari

pp. 315-327

BibTeX Abstract Full Text: PDF

Probably Approximate Learning of Sets and Functions

B. K. Natarajan

pp. 328-351

BibTeX Abstract Full Text: PDF

Efficient Parallel Algorithms for Testing $k$ and Finding Disjoint $s$-$t$ Paths in Graphs

Samir Khuller and Baruch Schieber

pp. 352-375

BibTeX Abstract Full Text: PDF

Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks

Yehuda Afek and Eli Gafni

pp. 376-394

BibTeX Abstract Full Text: PDF

Good and Bad Radii of Convex Polygons

Peter Gritzmann, Laurent Habsieger, and Victor Klee

pp. 395-403

BibTeX Abstract Full Text: PDF

Erratum: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses

p. 404

BibTeX Abstract Full Text: PDF